package com.leetcode.partition3;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author `RKC`
 * @date 2021/10/16 9:07
 */
public class LC282给表达式添加运算符 {

    private static final String[] operators = {"+", "-", "*"};

    public static List<String> addOperators(String num, int target) {
//        List<String> answer = new ArrayList<>();
//        backtracking(answer, num, 1, target, 0);
//        System.out.println(answer.size());
//        return answer;
        List<String> answer = new ArrayList<>();
        backtracking(answer, num, new StringBuilder(), 0, 0, 0, target);
        return answer;
    }

    public static void main(String[] args) {
        String num = "105";
        int target = 5;
        System.out.println(addOperators(num, target));
    }

    /**
     * @param answers 结果集
     * @param num 数字字符串
     * @param expression 拼接的表达式
     * @param startIndex 枚举到num的当前第startIndex个数字
     * @param res 当前表达式计算的结果
     * @param mul 表达式最后一个连乘串的计算结果
     */
    private static void backtracking(List<String> answers, String num, StringBuilder expression, int startIndex, long res, long mul, int target) {
        if (startIndex == num.length()) {
            if (res == target) answers.add(expression.toString());
            return;
        }
        int signalIndex = expression.length();
        //占位符，后面填充运算符
        if (signalIndex > 0) expression.append(0);
        long val = 0;
        // 枚举截取的数字长度（取多少位），注意数字可以是单个 0 但不能有前导零
        for (int i = startIndex; i < num.length() && (i == startIndex || num.charAt(startIndex) != '0'); i++) {
            val = val * 10 + num.charAt(i) - '0';
            expression.append(num.charAt(i));
            //表达式开始位置不能添加符号
            if (startIndex == 0) {
                backtracking(answers, num, expression, i + 1, val, val, target);
            } else {
                expression.setCharAt(signalIndex, '+');
                backtracking(answers, num, expression, i + 1, res + val, val, target);
                expression.setCharAt(signalIndex, '-');
                backtracking(answers, num, expression, i + 1, res - val, -val, target);
                expression.setCharAt(signalIndex, '*');
                backtracking(answers, num, expression, i + 1, res - mul + mul * val, mul * val, target);
            }
        }
        expression.setLength(signalIndex);
    }

    //--------------------回溯+表达式求值------------------
    private static void backtracking(List<String> answers, String expression, int startIndex, int target, int operatorCount) {
        if (operatorCount > 0) {
            boolean hasPrefixZero = false;
            //对表达式进行前导零检查
            for (int i = 0; i < expression.length(); i++) {
                if (expression.charAt(i) == '0' && i - 1 >= 0 && i + 1 < expression.length() && Character.isDigit(expression.charAt(i + 1)) && !Character.isDigit(expression.charAt(i - 1))) {
                    hasPrefixZero = true;
//                    System.out.println(expression + "有前导零");
                    break;
                }
            }
            if (!hasPrefixZero) {
//                System.out.println(expression);
                List<String> infix = convertInfixExpressionList(expression);
                List<String> suffix = convertSuffixExpression(infix);
                int ans = calculate(suffix);
                if (ans == target) answers.add(expression);
            }
        }
        for (int i = startIndex; i < expression.length(); i++) {
            String op1 = expression.substring(0, i);
            String op2 = expression.substring(i);
            for (String operator : operators) {
                backtracking(answers, op1 + operator + op2, i + 2, target, operatorCount + 1);
            }
        }
    }

    /**
     * 将中缀表达式字符串转化为List，考虑数字多位的情况
     */
    public static List<String> convertInfixExpressionList(String s) {
        List<String> result = new ArrayList<>();
        int i = 0;
        StringBuilder str;
        char c;
        do {
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
                //非数字
                result.add("" + c);
                i++;
                continue;
            }
            //数字，考虑多位数的问题
            str = new StringBuilder();
            while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                str.append(c);
                i++;
            }
            result.add(str.toString());
        } while (i < s.length());
        return result;
    }

    /**
     * 将中缀表达式转后缀表达式
     */
    private static List<String> convertSuffixExpression(List<String> infix) {
        Stack<String> operatorStack = new Stack<>();
        List<String> suffixList = new ArrayList<>();
        for (String operator : infix) {
            //数字的话直接加入后缀结果，如果是运算符时，与符号栈栈顶元素对比优先级，如果符号栈为空或者为左括号时，直接入栈
            //如果优先级比栈顶搞，也直接压入栈中，否则将栈顶元素弹出加入到结果中，直至栈顶元素不满足弹出要求
            if (operator.matches("\\d+")) suffixList.add(operator);
            else if ("(".equals(operator)) operatorStack.push(operator);
            else if (")".equals(operator)) {
                while (!"(".equals(operatorStack.peek())) {
                    suffixList.add(operatorStack.pop());
                }
                operatorStack.pop();
            } else {
                while (!operatorStack.isEmpty() && priority(operator) <= priority(operatorStack.peek())) {
                    suffixList.add(operatorStack.pop());
                }
                operatorStack.push(operator);
            }
        }
        while (!operatorStack.isEmpty()) {
            suffixList.add(operatorStack.pop());
        }
        return suffixList;
    }

    /**
     * 后缀表达式的计算
     */
    private static int calculate(List<String> suffix) {
        Stack<String> s = new Stack<>();
        for (String operator : suffix) {
            if (operator.matches("\\d+")) s.push(operator);
            else {
                int num1 = Integer.parseInt(s.pop());
                int num2 = Integer.parseInt(s.pop());
                int res = 0;
                switch (operator) {
                    case "+":
                        res = num1 + num2;
                        break;
                    case "-":
                        res = num2 - num1;
                        break;
                    case "*":
                        res = num1 * num2;
                        break;
                }
                s.push(String.valueOf(res));
            }
        }
        return Integer.parseInt(s.pop());
    }

    private static int priority(String operator) {
        if ("+".equals(operator) || "-".equals(operator)) return 1;
        if ("*".equals(operator) || "/".equals(operator)) return 2;
        return -1;
    }
}
